/***********************************
* 2、编写一个算法，根据一组输入的元素值建立一个递增的双向链表。
***********************************/

#include<stdio.h>
#include<malloc.h>

struct NODE;
typedef struct NODE node;
struct NODE{int data;node* next,*prev;};

void print_linkedlist(const node* p){
    p=p->next;
    while(p){printf("%d ",p->data);p = p->next;}
    putchar('\n');
}

void add_value_ascend_allow_repeat(node* h,int b){
    while(1){
        if(NULL == h->next || h->next->data >= b){
            node* p = malloc(sizeof(node));
            p->data = b;
            p->next = h->next;
            h->next = p;
            p->prev = h;
            return;
        }
        h = h->next;
    }
}

int main(){
    int n = 0,i,buf;
    node head;
    node* h = &head;
    h->prev = NULL;
    h->next = NULL;

    scanf("%d",&n);
    for(i=0;i<n;i++){scanf("%d",&buf);add_value_ascend_allow_repeat(h,buf);}
    printf("List: "); print_linkedlist(h);

    node* p;
    while(h){p = h;h=h->next;free(p);}

    return 0;
}